#include <iostream>
#include <vector>
#include <utility>
#define INF INT_MAX / 2
using namespace std;
int main(void) {
    int vnums, arcnums;
    cout << "点数" << "边数" << endl;
    cin >> vnums >> arcnums;
    vector<vector<int>> adj(vnums, vector<int>(vnums, INF));
    vector<vector<int>> edges(arcnums, vector<int>(3, 0));
    // 弧尾 弧头 权值
    cout << "依次输入边" << endl;
    for (int i = 0; i < arcnums; ++i) {
        cout << "第" << i+1 << "条边" << endl;
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    // 把边录入邻接矩阵
    for (auto arc: edges) {
        adj[arc[0]][arc[1]] = arc[2];  // 有向图只写这一个就行
        adj[arc[1]][arc[0]] = arc[2]; // 无向图还要写这一行
    }

    vector<bool> selected(vnums, false);
    vector<int> dist(vnums, INF); // 当前点到索引点的最小值
    vector<int> parent(vnums, -1);
    

    cout << "起始点" << endl;
    int begin;
    cin >> begin;
    selected[begin] = true;
    dist[begin] = 0;
    for (int v = 0; v < vnums; ++v) {
        if (v != begin) { // 除去起始点的那些点
            dist[v] = adj[begin][v];
            parent[v] = begin;
        }
    }
    for (int t = 1; t < vnums; ++t) {
        int min = -1;
        for (int v = 0; v < vnums; ++v) {
            if (!selected[v]) {
                if (min == -1 || dist[v] < dist[min]) {
                    min = v;
                }
            }
        }
        if (min == -1) { // 单纯的为了双保险
            cout << min << endl;
            break;
        }
        cout << parent[min] << "->" << min << endl;
        selected[min] = true;
        for (int v = 0; v < vnums; ++v) {
            if (!selected[v]) {
                if (adj[min][v] < dist[v]) {
                    dist[v] = adj[min][v];
                    parent[v] = min;
                }
            }
        }
    }

    return 0;
}
// 测试数据
// 节点数 边数量 接下来的每一条边 出发节点
// 6 10  0 1 6  1 4 3  4 5 6  5 3 2  3 0 5  0 2 1  1 2 5  4 2 6  5 2 4  3 2 5  0
